class Node {
  constructor(data) {
    this.left = null
    this.right = null
    this.value = data
  }
}
// 前中后遍历，指的是根节点所在的位置
// 前序遍历：根结点 ---> 左子树 ---> 右子树
// 中序遍历：左子树 ---> 根结点 ---> 右子树
// 后序遍历：左子树 ---> 右子树 ---> 根结点
class BinarySearchTree {
  constructor() {
    this.root = null
  }
  // 根据父节点插入子节点
  insertNode(root, newNode) {
    // 如果新节点的值小于根节点，则放在左边
    if (newNode.value < root.value) {
      // left存在则递归调用，重新比较
      root.left ? this.insertNode(root.left, newNode) : (root.left = newNode)
    } else {
      // 大于放右边,right 存在则递归重新比较
      root.right ? this.insertNode(root.right, newNode) : (root.right = newNode)
    }
  }
  // 插入新节点
  insert(value) {
    let newNode = new Node(value)
    if (!this.root) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }
  // 删除某个节点
  // 先找到目标节点，然后删除
  removeNode(root, value) {
    if (!root) {
      return null
    }

    if (value < root.value) {
      // 目标节点比当前节点小，则在左子树上查找
      root.left = this.removeNode(root.left, value)
      // return root
    } else if (value > root.value) {
      // 目标节点比当前节点大，则在右子树上查找
      root.right = this.removeNode(root.right, value)
      // return root
    } else {
      // 找到后进行删除操作
      if (!root.left && !root.right) {
        // 左右子树不存在，直接删除
        root = null
      } else if (!root.right) {
        // 右子树不存在，直接返回左子树
        root = root.left
      } else if (!root.left) {
        // 左子树不存在，直接返回右子树
        root = root.right
      } else {
        // 左右子树都存在，找到右子树中最小的值(肯定大于左子树所有的值)补位
        let minRight = this.findMinNode(root.right)
        root.value = minRight.value
        // 重排补位后右子树的顺序
        root.right = this.removeNode(root.right, minRight.value)
      }
    }
    return root
  }
  remove(value) {
    if (this.root) {
      this.removeNode(this.root, value)
    }
  }
  findMinNode(root) {
    if (!this.left) {
      return root
    } else {
      return this.findMinNode(root.left)
    }
  }
  // 查找某个节点
  searchNode(root, value) {
    if (!root) {
      return null
    }

    if (value < root.value) {
      return this.searchNode(root.left, value)
    } else if (value > root.value) {
      return this.searchNode(root.right, value)
    } else {
      return root
    }
  }
  // 前序遍历
  preOrder(root) {
    if (root) {
      console.log(root.value)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
  }
  inOrder(root) {
    if (root) {
      this.preOrder(root.left)
      console.log(root.value)
      this.preOrder(root.right)
    }
  }
  postOrder(root) {
    if (root) {
      this.preOrder(root.left)
      this.preOrder(root.right)
      console.log(root.value)
    }
  }
}
